package main

import . "local/algorithm/util"

func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	mid := findMid(head)
	tmp := mid.Next
	mid.Next = nil
	left := sortList(head)
	right := sortList(tmp)

	return mergeTwoLinkedList(left, right)
}

func findMid(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	p, q := head, head
	for q.Next != nil && q.Next.Next != nil {
		p = p.Next
		q = q.Next.Next
	}

	return p
}

func mergeTwoLinkedList(left, right *ListNode) *ListNode {
	if left == nil {
		return right
	}

	if right == nil {
		return left
	}

	if left.Val < right.Val {
		left.Next = mergeTwoLinkedList(left.Next, right)
		return left
	}

	right.Next = mergeTwoLinkedList(left, right.Next)
	return right
}

func main() {
	list := GenerateLinkedList([]int{1, 3, 56, 6, 2})
	list = sortList(list)
	PrintLinkedList(list)
}
